package leetcode.editor.cn.q1_300.q50;

import leetcode.editor.cn.util.tree.bstree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 自己有思路了。。。但是写不出来，还是看了答案
 *
 * @author qidi
 * @date 2021-12-28 13:28:50
 */
class Q0095_UniqueBinarySearchTreesIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public List<TreeNode> generateTrees(int n) {
            if (n == 0) return new LinkedList<>();

            return process(1, n);
        }

        private List<TreeNode> process(int start, int end) {
            List<TreeNode> allTrees = new ArrayList<>();
            if (start > end) {
                allTrees.add(null);
                return allTrees;
            }

            for (int i = start; i <= end; i++) {
                // 所有可能都左右子树
                List<TreeNode> lefts = process(start, i - 1);
                List<TreeNode> rights = process(i + 1, end);

                for (TreeNode left : lefts) {
                    for (TreeNode right : rights) {
                        TreeNode node = new TreeNode(i);
                        node.left = left;
                        node.right = right;
                        allTrees.add(node);
                    }
                }
            }
            return allTrees;
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0095_UniqueBinarySearchTreesIi().new Solution();
        solution.generateTrees(2);
        solution.generateTrees(3);
        solution.generateTrees(4);
    }
}